這邊借用高魁良先生今年文章的結尾名稱,我覺得挺適合作為電腦對局系列文的結尾。
這次的電腦對局系列文可以分成五個部分,每篇都是有連貫性的(除了幾篇意外的小插曲),建議按照順序閱讀。
第一部分:簡介
Day2、3、4:介紹了電腦對局的類型、複雜度與小故事。
Day8:介紹了電腦對局競賽。
第二部分:搜尋演算法
Day5、6:使用Minimax Algorithm搭配審局函數做出簡單的對局AI。
Day7、9:利用Alpha-Beta Pruning、Scout Algorithm等方式進行剪枝,來優化程式效能。
Day10、11、12:著手分析通過優先展開較佳的走步來提昇剪枝效果,進階一點的Threat Space Search,還有不能不注意的Horizon Effect。
Day16:用Bouzy's 5/21 Algorithm實作圍棋的形勢判斷,也算是一種審局函數。
Day13、14:最後利用實作圍棋征子邏輯來複習前面所學的演算法。
第三部分:Monte Carlo Tree Search
這邊介紹MCTS花了比較多的篇幅,所以我把它切出來。
Day15、17、18:介紹了MCTS的原理與優化方式。
Day19、20:介紹AlphaGo與開源框架AlphaZero General。
第四部分:進階優化方式
這部分屬於網路上能找到的資料比較少,一般人很難接觸到的部分,還有像是Bitboard等實作細節,感覺都是透過比賽或是實驗室前輩的傳承,幾乎沒有看到網路上有相關學習資源。
Day21:棋盤的資料結構。
Day22:利用Transposition Table增加程式效能。
Day23、24:介紹開局庫與殘局庫。
Day25、26:實作蜜月橋牌殘局庫。
Day27:通過位元運算來增加程式效能。
第五部分:生活中的應用?!
Day28、29:這邊純屬娛樂,幫大家增加一些無用的知識,但是祭品文的部分是真的有在準備XDD。
希望這系列文章能對大家有幫助!有認真看完的人應該都能順利寫出屬於自己的對局AI吧!
雖然完賽了但我還是會慢慢回頭校稿,確保內容上沒有問題,如果有哪邊解釋不清也歡迎大家留言。
很多完全資訊的雙人對局的AI強度都已經遠超人類了,好像繼續變強意義也不大,但還是有很多值得研究的方向,像是圍棋就有許多後續的研究,比如棋風、棋評等,各種擬人化AI與教學用途的研究。
尤其是在擬人化這塊,我們需要的是能幫助人學習的AI,所以勢必會需要有符合人類需求的弱AI,但現在大部分弱AI的弱跟人類想像中的弱不太一樣,適時的加入一些傳統的演算法反而可以得到一些意外的驚喜。
對圍棋有興趣的話我蠻推薦可以看看池田心教授實驗室的論文,之前從他們的論文中得到許多的靈感。
除了雙人對局外還可以往多人對局發展,像是橋牌這種有隊友的遊戲,目前好像還沒有一個比較好的做法。
不完全資訊對局也還有很多尚未突破的,都是很棒的研究題目。
居然真的完賽了。
當初朋友說我寫這種又冷門又不是新手向的文章肯定沒人看,也不可能得獎的,勸我還是別寫了。
甚至在日本時,同行的友人也覺得我發瘋了,出來玩還在民宿裡趕稿,我真的是每天都有棄賽的心。
如果沒有山陀兒颱風,台北賺到兩天颱風假,如果沒有高魁良大大、阿鵝大大來留言,我早就已經棄賽了,這真的是在數百萬個我棄賽的未來中唯一完賽的結局。
要寫這種理論與實作都有的文章真的很有挑戰,一開始我還花很多時間做對局樹的圖,到後面愈來愈懶,比較遺憾的是很多本來想介紹的遊戲最後都沒寫到,還有單人對局、多人對局、不完全資訊對局的坑沒有補上,只好明年再來寫了(沒得獎明年就不寫了!)。
這邊給還沒參加過但未來想參加鐵人賽的朋友們一個誠心的建議,一定要先囤稿!
每天一篇是真的會死,每天寫到11點40幾分發文,然後接著趕明天的稿到半夜三點,隔天下班接著寫到11點多,日復一日,連同事都說我看起來很憔悴,只能說珍惜生命,提早寫稿。
感謝各位願意看我文章的讀者們。
感謝彥吉、玉山、俊豪、A粉學長、CGLemon、Shawn、Phoenix、GP大大、琛神、唐神、冠毅、玠宇等人幫我校稿跟給我意見。
謝謝指教,明年再來一局。
恭喜完賽!真的是很有愛的一個系列,第四部也著實讓人大開眼界。marsgoat 大大看來是科班出身(深厚的 lab 傳承),文章寫起來技術含量比我那串高得多了。
能夠以資訊技術切入遊戲研究真的是幸福的。不完全資訊遊戲也是讓人興奮的未來方向。記得兩年多年在 survey 的時候,看到 [2020 這篇](The hanabi challenge: A new frontier for ai research)以花火當作下一個巨大的挑戰,現在引用數也破 400 了...
不過我最感興趣的還是變體,還有 AI 到底該怎麼隨著變體應對、去進行遊戲?像星際探險隊系列,一代很單純是規定誰應該吃到哪張/哪些牌(也就變相規定其他隊友不該吃到哪些牌),但是二代開始有各種規則,像是「必須和隊長吃到一樣墩數」、「在最後一敦吃到綠2」之類;不知道拼出一個 encoding 比較簡單,還是直接試著整合 LLM 比較簡單?...只是閒聊。
看到深厚的lab傳承,這句我真的是太慚愧了,當年都只學到些皮毛,今年老師退休,希望lab的傳承不會斷掉,努力把我能想到的都寫下來(雖然我前面的文章還很多要修的XD)。
完賽後終於有時間能回頭細看大大的文章了,假日來研究一下看怎麼幫忙改進!